package org.example.myleet.rosalind.cat;

import org.example.myleet.rosalind.utils.FastaReader;

import java.util.HashMap;
import java.util.Map;

public class Solution {

    private static final int MOD_BASE = 1000000;

    public static void main(String[] args) {
        Solution solution = new Solution();
//        int count = solution.countCrossingPerfectMatching(FastaReader.parseFastaInput(">Rosalind_57\n" +
//                "AUAU\n").get(0).getSequence());
//        int count = solution.countCrossingPerfectMatching(FastaReader.parseFastaInput(">Rosalind_57\n" +
//                "AUCGCGAU\n").get(0).getSequence());
//        int count = solution.countCrossingPerfectMatching(FastaReader.parseFastaInput(">Rosalind_57\n" +
//                "AUAUAU\n").get(0).getSequence());
//        int count = solution.countCrossingPerfectMatching(FastaReader.parseFastaInput(">Rosalind_57\n" +
//                "AUAUAUAU\n").get(0).getSequence());
        int count = solution.countCrossingPerfectMatching(FastaReader.parseFastaInput(">Rosalind_7723\n" +
                "UGGCCCACGUGCAUAUGAGCUGCUGAUUGAUACGUCAGGCCUGCACAGCAUUGCGCGCGG\n" +
                "CCCGGAGCUCCGAACGCACGUGCCGGUAAUUACUAGUGCGCGUACGUACAAUUAUAUGUA\n" +
                "GCCGCGCAUGGAUCAUGCAGCUCGACGCAUGUAGGCCACGUCGCGACGCGUAAUUUAUAG\n" +
                "CUAUCUGCAAUAUCUGAUCACGUACGGAUAUCGAUUUAUACGUUAAGCGCAAUAUGAUCC\n" +
                "GACUGCGCCAUGAGCG\n").get(0).getSequence());
        System.out.println(count);
    }

    private Map<String, Integer> memo;

    public Solution() {
        memo = new HashMap<>();
    }

    public int countCrossingPerfectMatching(String sequence) {
        //记忆化搜索
        Integer count = memo.get(sequence);
        if (null != count) {
            return count;
        }
        count = 0;
        if (2 == sequence.length()) {
            //长度为2的情况，直接计算
            char c0 = sequence.charAt(0);
            char c1 = sequence.charAt(1);
            if (c0 == 'A' && c1 == 'U' || c0 == 'U' && c1 == 'A') {
                //A-U或U-A结合
                count = 1;
            }
            if (c0 == 'C' && c1 == 'G' || c0 == 'G' && c1 == 'C') {
                //C-G或G-C结合
                count = 1;
            }
            memo.put(sequence, count);
            return count;
        }
        //将0和第i个位置进行连接，将字符串分成左右两半，如果可以进行这样的切分，则结果为左右两半的子问题答案相乘
        //每一半变成一个新的字符串，问题规模缩小为求子问题的答案，递归进行计算子问题
        for (int i = 1; i < sequence.length(); i += 2) {
            //先检查第0和第i个位置能够进行base pair连接，A-U或C-G，不能形成氢键的则跳过
            char c0 = sequence.charAt(0);
            char ci = sequence.charAt(i);
            if (c0 == 'A') {
                if (ci != 'U') {
                    continue;
                }
            } else if (c0 == 'C') {
                if (ci != 'G') {
                    continue;
                }
            } else if (c0 == 'G') {
                if (ci != 'C') {
                    continue;
                }
            } else if (c0 == 'U') {
                if (ci != 'A') {
                    continue;
                }
            }
            //找到一种方案将字符串分成两半，则进行递归做子问题求解
            int cLeft = 1;
            if (i > 1) {
                cLeft = countCrossingPerfectMatching(sequence.substring(1, i));
                if (0 == cLeft) {
                    continue;
                }
            }
            cLeft %= MOD_BASE;
            int cRight = 1;
            if (i < sequence.length() - 2) {
                cRight = countCrossingPerfectMatching(sequence.substring(i + 1));
                if (0 == cRight) {
                    continue;
                }
            }
            cRight %= MOD_BASE;
            //下面求两边的子问题答案相乘结果，小心有坑就是两个10^5数字相乘可能会溢出，需要用long保存计算结果
            long m = (long) cLeft * (long) cRight;
            count += (int) (m % MOD_BASE);
            count %= MOD_BASE;
        }
        //记忆化问题结果
        memo.put(sequence, count);
        return count;
    }
}
